In computer graphics systems, three-dimensional objects are often defined as a set of polygons, which are projected to a two-dimensional screen space, e.g., a screen of a computer monitor, to give the illusion of depicting a three-dimensional object therein. For added three-dimensional realism, the polygons are "covered" with a texture that is scaled to the shape of the polygon. The operation that combines a polygon with a particular texture is known in the art as texture mapping. Specifically, a texture mapping operation combines a scaled and transformed polygon with a similarly scaled and transformed texture to achieve an illusion of three-dimensionality within a two-dimensional screen space.
Textures are typically stored in memory within the graphics system as a set of identical images each having a different level of resolution. Such an arrangement of textures is known as an image pyramid. The resolution of successive levels of a pyramid differ by a power of two such that each successive level of the pyramid has one-quarter of the pixels contained in the previous (underlying) level. In many graphics systems, each texture is represented by a plurality of color pyramids, e.g., a red pyramid, a green pyramid and a blue pyramid. Thus, for each pixel value required in the output image, or required to compute a pixel value in the output image, the graphics system produces three memory addresses and accesses three memory locations.
To generate a texture that is correctly scaled to a projected polygon, three address values for each pyramid are used to produce a pixel value at a correct location within the polygon. These values are U and V, representing Cartesian coordinates into a base image, i.e., the base of the image pyramid, and D, representing a pyramid level. As such, U, V, and D define a location of a particular pixel value within a particular image pyramid, e.g., a red pyramid.
In some instances, a pixel value necessary to produce an accurate output image may have coordinates that lie between actual pixel locations in a given level of a pyramid. Furthermore, the necessary pixel value may require a resolution that lies between levels. Consequently, the texture mapping function interpolates the nearest pixel values to determine the unknown pixel value. Specifically, for pixel values that are defined between levels of the pyramid, four pixel values in a level above the target pixel location and four pixel values below the target pixel location are tri-linearly interpolated to produce the target pixel value for the target location in an output image.
Present operations for generating locations (addresses) in memory for the eight pixel values used in the tri-linear interpolation typically require many computing cycles. Thus, the pixel selection process is relatively slow.
Therefore, a need exists in the art for an efficient apparatus and method for rapidly generating addresses of pixel values in an image pyramid.